home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1992 June: ROMin Holiday / ADC Developer CD (1992-06) (''ROMin Holiday'')_iso / Developer Connection - 06-1992.iso / Periodicals / develop / develop 10 code / Picture Utilities / Octree Source / octree.c
Encoding:
C/C++ Source or Header  |  1992-04-08  |  26.5 KB  |  745 lines  |  [TEXT/KAHL]
  1. #include <MacHeaders>
  2. #include <PictUtil.h>
  3.  
  4.  
  5.  
  6. /*    compile-time switches. during the course of developing this custom sampling method, we found it useful to have a
  7.     bunch of debugging code that checks for invalid data structures compiled into strategic spots in the code. however,
  8.     since the debugging code slows the method down by several orders of magnitude, we made all of it conditional on
  9.     the following “debugging” flag. simply change the undef to a define and then all the debugging code will be compiled
  10.     in to allow you to test your changes. */
  11.  
  12. #undef debugging
  13.  
  14.  
  15.  
  16. /* constants that we use throughout the code */
  17.  
  18. #define    emptyNode        0x8000        /* this indicates that either a child or a parent slot doesn’t point to any node */
  19. #define    obsoleteNode        0xFFFF        /* this value stored in the “children” field of a node, indicates that it needs to be removed */
  20. #define    maximumLevel        8            /* this is the maximum number of levels that the octree covers */
  21.  
  22.  
  23.  
  24. /* macros used for conditionally compiling debugging code */
  25.  
  26. #ifdef debugging
  27.     #define    IfDebug(x, y)        { if(x) DebugStr(y); }
  28.     #define    ValidateTree(x)        ValidateOctree(x)
  29. #else
  30.     #define    IfDebug(x, y)
  31.     #define    ValidateTree(x)
  32. #endif
  33.  
  34.  
  35.  
  36. /* the data structures used by this sampling method */
  37.  
  38. typedef struct octreeNode {
  39.     short    children;            /* count of how many leaves are filled */
  40.     short    parent;
  41.     short    leaf[8];
  42. } octreeNode;
  43.  
  44. typedef struct octreeColor {
  45.     long            count;
  46.     unsigned long    totalRed;        /* this total allows us to average all the components of this entry */
  47.     unsigned long    totalGreen;
  48.     unsigned long    totalBlue;
  49.     short        level;
  50.     short        next;        /* color index of the next color at this level */
  51.     short        parent;        /* node index of the node that owns this color */
  52.     short        padding;        /* to make the structure long aligned */
  53. } octreeColor;
  54.  
  55. typedef struct octree {
  56.     short        maximumNodes;
  57.     short        nodes;
  58.     octreeNode    *nodeBase;
  59.     short        maximumColors;
  60.     short        colors;
  61.     octreeColor    *colorBase;
  62.     short        validationCount;
  63.     short        colorList[maximumLevel + 1];    /* these are indexes into the first color entry at this level (zero is allocated, but unused)*/
  64. } octree;
  65.  
  66.  
  67. /*-------------------------------------------------------------------------------------------------------*/
  68. /*    this is the code for a custom color sampling method that can be called by picture utilities to determine the best
  69.     set of colors to use for a picture. it uses a data structure known as an octree to keep track of its colors following
  70.     a method loosely described in Graphics Gems on page 287 by Michael Gervautz and Werner Purgathofer.
  71.  
  72.     picture utilities will store one long word for us and pass it to each of our routines, so we use this to store a handle
  73.     to our main octree structure. we lock and dereference this handle upon entering each of the “public” routines that
  74.     picture utilities calls and we unlock it upon exiting these routines. note that since we don’t allocate memory in any
  75.     of the internal octree routines, we wouldn’t really need to lock this handle down, but locking it doesn’t cost us any
  76.     measurable time and allows us to change the internals later to allocate memory without being bitten by a memory
  77.     bug.
  78.  
  79.     we also have two other handles; one for the maximum number of nodes that we would ever need to allocate and the
  80.     other for the colors that we will return. we need one more slot than the number of colors requested, because the
  81.     algorithm inserts every new color that it finds and only then does it check to see if we have too many colors and
  82.     we need to reduce the octree.
  83.  
  84.     the standard way of working with octree nodes is to have eight pointers in each node to the various children of
  85.     that node. however, in an effort to reduce the storage requirements (and not burden the memory manager with
  86.     too many blocks), we have chosen to use indices into the nodeBase array for each of the children. a child of a node
  87.     can either be a color or another node and since these two types of objects are different sizes and stored in
  88.     different arrays, we use the convention of negative numbers to indicate that the bitwise not of the child index is
  89.     an index into the color table and positive numbers to indicate that the child index is an index into the node table.
  90.     there is also a special constant (emptyNode) to indicate that a child entry is empty.
  91.  
  92.     each node and color keeps an index to its parent node, which greatly speeds up the reduction process. nodes also
  93.     keep a count of their children, although this isn’t as much of a win for the reduction process.
  94.  
  95.     the way the algorithm works is that for every color, we call AddColorToOctree, which walks down all the nodes,
  96.     until it finds the correct slot for the color. to determine the correct slot, we use only the high byte of each
  97.     component, which we sucessively shift as we walk through the tree, using the highest bit of each component to
  98.     select which child of the node to look at. if the child node is empty and we haven’t reached our maximum level
  99.     yet, we create a new node and continue the add process. if we have reached our maximum level, then we create
  100.     a new color and save our color-to-add there. if the child entry points to an already existing color, then we add
  101.     our new color to the accumulating totals in the color entry and return.
  102.  
  103.     after adding a new color, we check to see if the number of colors in the tree is greater than the number requested.
  104.     if this is the case, then we call ReduceOctree, which in a very simplistic way, combines two existing color entries
  105.     into one that spans a broader section of the RGB cube.
  106.  
  107.     when picture utilities asks us for the color table, we can return it directly out of our colorBase array, since the
  108.     octree has been being trimmed as we go.
  109.  
  110.     much of the code for this method is concerned with the reduction process. reduction is a bit tricky since we don’t
  111.     keep pointers to children and we don’t allow gaps in either our node structure or our color structure. this has the
  112.     benefit of allowing us to avoid allocating or deallocating any memory while we are recording colors, but we have
  113.     to have code to deal with things like removing a color (or a node) from the middle of the colorBase array. we do
  114.     so by copying the last color (or node) over the item that we are removing and then updating that item’s parent to
  115.     point to the new spot. if the item is a color, then we also need to walk the colorList for the correct level and re-
  116.     link the chain of colors to skip the removed one.
  117.  
  118.     the colorList arrays are convenient in determining where to start combining nodes during reduction. there is an
  119.     array for each level and when we need to reduce colors, we always start with the maximumLevel array (level
  120.     eight) and we try to reduce the first item in it. if that color’s parent had more than one child, then we can save
  121.     a color by combining all the children of this parent into a single averaged color and we imediately proceed to do
  122.     so. if the parent has only one child, then we move to the next color in the colorList for that level. only when we
  123.     are unable to reduce any colors in a given level do we move up to the colorList array for the previous level and
  124.     try to reduce colors from it.
  125.  
  126.     when we move up a level, we must also remember to try reducing the next level’s colors by two levels, before
  127.     actually giving up are proceeding up another level. for example, we might have 3 level 8 colors that can’t be
  128.     reduced to level 7 (or at least we wouldn’t gain a color) and 5 level 7 nodes that also can’t be reduced. after
  129.     checking the last level 7 node, we would look again at the level 8 nodes, this time trying to reduce them all the
  130.     way up to level 6, where they would encompass sixty-four level 8 RGB cubes. if we can save a color by reducing
  131.     a level 8 color two levels up to level six, we will do so before proceeding to the level 6 list and trying to reduce
  132.     level 6 colors to level 5.
  133.  
  134.     there is lots of room for improvement in the algorithm that choses which colors to reduce. currently, we don’t
  135.     look at all at the number of source codes combined into a color entry; this lets us preserve small splashes of a
  136.     drasticly different color at the cost of muddying up the colors that make up the bulk of the image.
  137.  
  138.     note that we remove colors immediately when we combine them, but we only mark nodes as obsolete without
  139.     removing them on the spot. this is solely because the ReduceNode routine is recursive and keeps which node
  140.     it is working with on the stack. this would be a problem if while removing a node, we need to reorder the nodes
  141.     that are referenced by different incarnations of ReduceNode. by marking all the nodes as obsolete, we can
  142.     postpone removing them until no-one has any references (besides the tree structure itself) and it is safe to
  143.     move nodes.
  144. */
  145. /*-------------------------------------------------------------------------------------------------------*/
  146.  
  147.  
  148. /* function prototypes for the main subroutines that picture utilities will call. */
  149.  
  150. pascal short InitOctree(short colorsRequested, long *dataHandlePtr, short *bankType);
  151. pascal short RecordOctreeColors(long dataHandle, RGBColor *colorPtr, long colorCount, long *uniqueColorsPtr);
  152. pascal short CalcOctreeTable(long dataHandle, short colorsRequested, short *colorBankPtr, ColorSpec *resultPtr);
  153. pascal short KillOctree(long dataHandle);
  154.  
  155.  
  156.  
  157. /* our main dispatcher. picture utilities will call this with the selector for which pick function to call in D0.w */
  158. void main(void)
  159. {
  160.     asm {
  161.         lsl.w        #2, d0
  162.         lea        @table, a0
  163.         jmp        0(a0, d0.w)
  164.  
  165. @table    jmp        InitOctree
  166.         jmp        RecordOctreeColors
  167.         jmp        CalcOctreeTable
  168.         jmp        KillOctree
  169.     }
  170. }
  171.  
  172.  
  173. /*    these functions validate the main octree structure to make sure that all the nodes point to valid entries in either the
  174.     node table or in the color table. they also make sure that each node’s (or color’s) parent field really does point to the
  175.     node that contains them and they ensure that all the color lists (one for each level) contain only colors that are valid
  176.     entries in the color table */
  177.  
  178. #ifdef debugging
  179.     static void ValidateNode(octree *tree, octreeNode *node)
  180.     {
  181.         short counter = 8;
  182.         short nodeIndex;
  183.  
  184.         IfDebug(node->children > 8, "\ptoo many children in node");
  185.         IfDebug(node->parent != emptyNode && node->parent >= tree->nodes, "\pinvalid node parent");
  186.  
  187.         nodeIndex = node - &tree->nodeBase[0];
  188.         while( --counter >= 0 ) {
  189.             short childIndex = node->leaf[counter];
  190.             if( childIndex != emptyNode ) {
  191.                 if( childIndex >= 0 ) {
  192.                     octreeNode *child;
  193.                     IfDebug(childIndex >= tree->nodes, "\pinvalid node child");
  194.                     child = &tree->nodeBase[childIndex];
  195.                     if( child->children != obsoleteNode ) {
  196.                         IfDebug(child->parent != nodeIndex, "\pchild node doesnt belong to parent");
  197.                         ValidateNode(tree, child);
  198.                     }
  199.                 } else {
  200.                     octreeColor *child;
  201.                     childIndex = ~childIndex;
  202.                     IfDebug(childIndex >= tree->colors, "\pinvalid color child");
  203.                     child = &tree->colorBase[childIndex];
  204.                     IfDebug(child->parent != nodeIndex, "\pchild color doesnt belong to parent");
  205.                     IfDebug(child->level > maximumLevel, "\pcolor level is invalid");
  206.                     IfDebug(child->next != emptyNode && child->next >= tree->colors, "\pcolor next field is invalid");
  207.                 }
  208.             }
  209.         }
  210.     }
  211.  
  212.     static void ValidateColorList(octree *tree, short colorIndex)
  213.     {
  214.         short level = -1;
  215.         while( colorIndex != emptyNode ) {
  216.             octreeColor *color;
  217.             IfDebug(colorIndex >= tree->colors, "\pinvalid color in color list");
  218.             color = &tree->colorBase[colorIndex];
  219.             IfDebug(color->level > maximumLevel, "\pcolor level is invalid");
  220.             if( level < 0 )
  221.                 level = color->level;
  222.             IfDebug(color->level != level, "\pcolor not at same level as the rest of the list");
  223.             colorIndex = color->next;
  224.         }
  225.     }
  226.  
  227.     static void ValidateOctree(octree *tree)
  228.     {
  229.         octreeNode *node = &tree->nodeBase[0];
  230.         short counter;
  231.  
  232.         ++tree->validationCount;
  233.         IfDebug(node->children == obsoleteNode, "\pthe top node cannot be obsolete");
  234.         ValidateNode(tree, node);
  235.  
  236.         counter = maximumLevel + 1;
  237.         while( --counter > 0 )
  238.             ValidateColorList(tree, tree->colorList[counter]);
  239.     }
  240. #endif
  241.  
  242.  
  243. /*    this function is called to add each color to the octree */
  244.  
  245. static void AddColorToOctree(octree *tree, RGBColor *inputColor)
  246. {
  247.     char red = inputColor->red >> 8;
  248.     char green = inputColor->green >> 8;
  249.     char blue = inputColor->blue >> 8;
  250.     octreeNode *node = &tree->nodeBase[0];
  251.     short level = 0;
  252.     short index;
  253.  
  254.     ValidateTree(tree);
  255.     while( true ) {
  256.         short *childPtr;
  257.  
  258.         ++level;
  259.  
  260.     /*    use the red, green, and blue input components to determine which of the eight children of this node to look
  261.         at. then shift the components left by one bit to leave them setup for the next time through this loop. */
  262.  
  263.         index = 0;
  264.         if(red < 0)        index += 4;    red <<= 1;
  265.         if(green < 0)    index += 2;    green <<= 1;
  266.         if(blue < 0)    index += 1;    blue <<= 1;
  267.  
  268.     /*    get a pointer to the child in this node that we are going to look at. */
  269.  
  270.         childPtr = &node->leaf[index];
  271.         index = *childPtr;
  272.  
  273.         if( index == emptyNode ) {
  274.  
  275.             /* increment this node’s child count, since it now has children. then calculate the index of the parent node */
  276.             ++node->children;
  277.             index = node - &tree->nodeBase[0];
  278.  
  279.             if( level == maximumLevel ) {
  280.                 octreeColor *color;
  281.  
  282.                 IfDebug(tree->colors >= tree->maximumColors, "\pno room to create another color");
  283.  
  284.             /*    the child at this position was empty and we are at level eight (the deepest possible), so add the input
  285.                 color to the color table and set this child to “point” to this new color entry. note that indices that
  286.                 point to entries in the color table are negative to distinguish them from indices that point to entries
  287.                 in the node table. */
  288.  
  289.                 *childPtr = ~tree->colors;
  290.                 color = &tree->colorBase[tree->colors];
  291.                 color->count = 1;
  292.                 color->totalRed = inputColor->red;
  293.                 color->totalGreen = inputColor->green;
  294.                 color->totalBlue = inputColor->blue;
  295.  
  296.                 color->level = level;
  297.                 color->next = tree->colorList[level];
  298.                 color->parent = index;
  299.                 tree->colorList[level] = tree->colors;
  300.                 ++tree->colors;
  301.                 return;
  302.             }
  303.  
  304.             IfDebug(tree->nodes >= tree->maximumNodes, "\pno room to create another node");
  305.  
  306.         /*    create a new node here and set this child to “point” to this new color entry. next clear all the fields of
  307.             the new node. */
  308.  
  309.             *childPtr = tree->nodes;
  310.             node = &tree->nodeBase[tree->nodes];
  311.             node->children = 0;
  312.             node->parent = index;
  313.             node->leaf[0] = emptyNode;
  314.             node->leaf[1] = emptyNode;
  315.             node->leaf[2] = emptyNode;
  316.             node->leaf[3] = emptyNode;
  317.             node->leaf[4] = emptyNode;
  318.             node->leaf[5] = emptyNode;
  319.             node->leaf[6] = emptyNode;
  320.             node->leaf[7] = emptyNode;
  321.             ++tree->nodes;
  322.             continue;
  323.  
  324.         } else if( index < 0 ) {
  325.             octreeColor *color = &tree->colorBase[~index];
  326.  
  327.         /*    the child at this position was a color so add the input color to the total color for this entry and increment
  328.             the count. we can use these values at the end of the process to calculate an average color for this entry.
  329.             note that these totals will overflow when more than 65536 pixels with large components (greater than
  330.             65000) are all in this box; we aren’t going to worry about this, for now. */
  331.  
  332.             ++color->count;
  333.             color->totalRed += inputColor->red;
  334.             color->totalGreen += inputColor->green;
  335.             color->totalBlue += inputColor->blue;
  336.             return;
  337.         }
  338.  
  339.         IfDebug(index >= tree->nodes, "\ppast the end of the octree");
  340.         node = &tree->nodeBase[index];
  341.     }
  342. }
  343.  
  344.  
  345. static void RemoveColorFromLevel(octree *tree, short colorIndex)
  346. {
  347.     octreeColor *color = &tree->colorBase[colorIndex];
  348.  
  349.     IfDebug(colorIndex >= tree->colors, "\pcolor to remove doesnt exist");
  350.  
  351.     if( tree->colorList[color->level] == colorIndex )
  352.         tree->colorList[color->level] = color->next;
  353.     else {
  354.         short index = tree->colorList[color->level];
  355.  
  356.         while( index != emptyNode ) {
  357.             color = &tree->colorBase[index];
  358.             IfDebug(index >= tree->colors, "\pcolor in color list doesnt exist");
  359.             if( color->next == colorIndex ) {
  360.                 color->next = tree->colorBase[color->next].next;
  361.                 return;
  362.             }
  363.             index = color->next;
  364.         }
  365.  
  366.         IfDebug(1, "\pcolor to remove is not in this level list");
  367.     }
  368. }
  369.  
  370.  
  371. /*    this function removes the color specified by newIndex from the octree. since the color table in the octree cannot have
  372.     gaps, removing this color really consists of moving the last color in the octree to the position occupied by newIndex
  373.     and then reducing the total color count. since the nodes in the octree reference this last color once somewhere, we
  374.     must scan through all the nodes until we find the one that does reference it and update its leaf entry to index to the
  375.     new position of this color. this function also keeps track of where the color pointed to by preserveColor moves to
  376.     (if it does move) and it returns this new location. */
  377.  
  378. static octreeColor *RemoveColor(octree *tree, short newIndex, octreeColor *preserveColor)
  379. {
  380.     short oldIndex;
  381.  
  382.     ValidateTree(tree);
  383.     RemoveColorFromLevel(tree, newIndex);
  384.  
  385. /*    if we are removing the last color, then there is no reordering to do, so simply return. */
  386.  
  387.     oldIndex = --tree->colors;
  388.     if( oldIndex == newIndex )
  389.         return preserveColor;
  390.  
  391.     IfDebug(newIndex > oldIndex, "\pattempting to remove a color that doesnt exist");
  392.  
  393. /*    if the color we are moving (the last color) is the one whose pointer we need to preserve, then reset its pointer
  394.     to its new location. then copy the color structure from the old position to the new one. */
  395.  
  396.     if( &tree->colorBase[oldIndex] == preserveColor )
  397.         preserveColor = &tree->colorBase[newIndex];
  398.     tree->colorBase[newIndex] = tree->colorBase[oldIndex];
  399.  
  400. /*    look at the color we are moving (the last color) and get its level. then scan through all the colors in the list for
  401.     this level looking for the one that we renumbered. when we find it, then we renumber it. */
  402.  
  403.     {    octreeColor *color = &tree->colorBase[oldIndex];
  404.         if( tree->colorList[color->level] == oldIndex ) {
  405.             tree->colorList[color->level] = newIndex;
  406.         } else {
  407.             short levelIndex = tree->colorList[color->level];
  408.             while( levelIndex != emptyNode ) {
  409.                 color = &tree->colorBase[levelIndex];
  410.                 IfDebug(levelIndex > tree->colors, "\pcolor in color list doesnt exist");
  411.                 if( color->next == oldIndex ) {
  412.                     color->next = newIndex;
  413.                     break;
  414.                 }
  415.                 levelIndex = color->next;
  416.             }
  417.         }
  418.     }
  419.  
  420. /*    look at the color we are moving (the last color) and get its parent node. then scan through all the children of this
  421.     parent to find the entry that points to the old location and update it to contain the index of the new location. */
  422.  
  423.     {    octreeColor *color = &tree->colorBase[newIndex];
  424.  
  425.         if( color->parent != emptyNode ) {
  426.             octreeNode *node = &tree->nodeBase[color->parent];
  427.             short counter = 8;
  428.  
  429.             IfDebug(color->parent >= tree->nodes, "\pcolor has an invalid parent");
  430.             IfDebug(node->children == obsoleteNode, "\pcolors parent is obsolete");
  431.  
  432.             oldIndex = ~oldIndex;
  433.             while( --counter >= 0 ) {
  434.                 if( node->leaf[counter] == oldIndex ) {
  435.                     node->leaf[counter] = ~newIndex;
  436.                     ValidateTree(tree);
  437.                     return preserveColor;
  438.                 }
  439.             }
  440.             IfDebug(1, "\pcant find last color in its parent node");
  441.         }
  442.     }
  443.  
  444.     return preserveColor;
  445. }
  446.  
  447.  
  448. static octreeColor *ReduceNode(octree *tree, octreeNode *base, octreeColor *resultColor)
  449. {
  450.     short index;
  451.     short counter = 8;
  452.  
  453.     ValidateTree(tree);
  454.     while( --counter >= 0 ) {
  455.         index = base->leaf[counter];
  456.         if( index == emptyNode )
  457.             continue;
  458.         if( index >= 0 ) {
  459.             IfDebug(index >= tree->nodes, "\pattempting to reduce a node that doesnt exist");
  460.             resultColor = ReduceNode(tree, &tree->nodeBase[index], resultColor);
  461.         } else {
  462.             octreeColor *newColor = &tree->colorBase[~index];
  463.             IfDebug(~index >= tree->colors, "\pattempting to remove a color that doesnt exist");
  464.             if( resultColor != newColor ) {
  465.                 base->leaf[counter] = emptyNode;
  466.                 newColor->parent = emptyNode;
  467.                 resultColor->count += newColor->count;
  468.                 resultColor->totalRed += newColor->totalRed;
  469.                 resultColor->totalGreen += newColor->totalGreen;
  470.                 resultColor->totalBlue += newColor->totalBlue;
  471.                 resultColor = RemoveColor(tree, ~index, resultColor);
  472.             }
  473.         }
  474.     }
  475.     base->children = obsoleteNode;
  476.     ValidateTree(tree);
  477.     return resultColor;
  478. }
  479.  
  480.  
  481. static void RemoveObsoleteNodes(octree *tree)
  482. {
  483.     octreeNode *outerNode = &tree->nodeBase[0];
  484.     short outerNodes = tree->nodes;
  485.  
  486.     ValidateTree(tree);
  487.  
  488.     while( --outerNodes >= 0 ) {
  489.         if( outerNode->children == obsoleteNode ) {
  490.             octreeNode *node = outerNode;
  491.             octreeNode *parent;
  492.             short newIndex = outerNode - &tree->nodeBase[0];
  493.             short oldIndex;
  494.             short counter;
  495.  
  496.             while( node->children == obsoleteNode ) {
  497.                 oldIndex = (--outerNodes, --tree->nodes);
  498.                 if( outerNodes < 0 ) {
  499.                     ValidateTree(tree);
  500.                     return;
  501.                 }
  502.                 node = &tree->nodeBase[oldIndex];
  503.             }
  504.  
  505.             parent = &tree->nodeBase[node->parent];
  506.  
  507.             counter = 8;
  508.             while( --counter >= 0 ) {
  509.                 if( parent->leaf[counter] == oldIndex ) {
  510.                     parent->leaf[counter] = newIndex;
  511.                     goto fixChildren;
  512.                 }
  513.             }
  514.             IfDebug(1, "\pcant find the node we are moving in its parents list of children");
  515. fixChildren:
  516.             counter = 8;
  517.             while( --counter >= 0 ) {
  518.                 short index = node->leaf[counter];
  519.                 if( index == emptyNode )
  520.                     continue;
  521.                 if( index >= 0 ) {
  522.                     octreeNode *child = &tree->nodeBase[index];
  523.                     IfDebug(child->parent != oldIndex, "\pchild does not point back to correct parent");
  524.                     child->parent = newIndex;
  525.                 } else {
  526.                     octreeColor *child = &tree->colorBase[~index];
  527.                     IfDebug(child->parent != oldIndex, "\pchild does not point back to correct parent");
  528.                     child->parent = newIndex;
  529.                 }
  530.             }
  531.  
  532.             tree->nodeBase[newIndex] = tree->nodeBase[oldIndex];
  533.         }
  534. next:    ++outerNode;
  535.     }
  536.     ValidateTree(tree);
  537. }
  538.  
  539.  
  540. static void ReduceOctree(octree *tree)
  541. {
  542.     octreeColor *color;
  543.     octreeNode *node;
  544.     short level;
  545.     short index;
  546.  
  547.     if( tree->colors < tree->maximumColors )
  548.         return;
  549.  
  550.     ValidateTree(tree);
  551.     level = maximumLevel;
  552.     while( level > 0 ) {
  553.         short innerLevel = level;
  554.  
  555.         while( innerLevel <= maximumLevel ) {
  556.             index = tree->colorList[innerLevel];
  557.             while( index != emptyNode ) {
  558.                 short parentIndex;
  559.  
  560.                 IfDebug(index >= tree->colors, "\pinvalid color in the color list");
  561.                 color = &tree->colorBase[index];
  562.                 parentIndex = color->parent;
  563.                 IfDebug(parentIndex >= tree->nodes, "\pcolor has invalid parent");
  564.                 node = &tree->nodeBase[parentIndex];
  565.  
  566.                 {    short tempLevel = innerLevel;
  567.                     while( tempLevel > level ) {
  568.                         parentIndex = node->parent;
  569.                         IfDebug(parentIndex >= tree->nodes, "\pnode has invalid parent");
  570.                         node = &tree->nodeBase[parentIndex];
  571.                         --tempLevel;
  572.                     }
  573.                 }
  574.  
  575.                 if( node->children > 1 ) {
  576.                     octreeNode *parent = &tree->nodeBase[node->parent];
  577.                     short counter = 8;
  578.                     while( --counter >= 0 ) {
  579.                         if( parent->leaf[counter] == parentIndex ) {
  580.                             short colorIndex;
  581.  
  582.                         /* orphan the color from its parent */
  583.  
  584.                             {    octreeNode *colorParent = &tree->nodeBase[color->parent];
  585.                                 short counter = 8;
  586.                                 colorIndex = ~(color - &tree->colorBase[0]);
  587.                                 while( --counter >= 0 ) {
  588.                                     if( colorParent->leaf[counter] == colorIndex ) {
  589.                                         colorParent->leaf[counter] = emptyNode;
  590.                                         goto orphanColor;
  591.                                     }
  592.                                 }
  593.                                 IfDebug(1, "\pcouldnt find color in parent");
  594.                             }
  595. orphanColor:                    color->parent = emptyNode;
  596.                             ValidateTree(tree);
  597.  
  598.                             color = ReduceNode(tree, node, color);
  599.                             ValidateTree(tree);
  600.                             colorIndex = color - &tree->colorBase[0];
  601.                             RemoveColorFromLevel(tree, colorIndex);
  602.                             color->level = level - 1;
  603.                             color->parent = parent - &tree->nodeBase[0];
  604.                             parent->leaf[counter] = ~colorIndex;
  605.                             color->next = tree->colorList[level - 1];
  606.                             tree->colorList[level - 1] = colorIndex;
  607.                             RemoveObsoleteNodes(tree);
  608.                             return;
  609.                         }
  610.                     }
  611.                     IfDebug(1, "\pcant find node in parent");
  612.                 }
  613.                 index = color->next;
  614.             }
  615.             ++innerLevel;
  616.         }
  617.  
  618.         --level;
  619.     }
  620.  
  621.     IfDebug(1, "\punable to reduce the octree");
  622. }
  623.  
  624.  
  625. pascal short InitOctree(short colorsRequested, long *dataHandlePtr, short *bankType)
  626. {
  627.     octree *tree;
  628.     octreeNode *node;
  629.     Handle dataHandle, tempHandle;
  630.     short counter;
  631.  
  632.     if( colorsRequested < 4 || colorsRequested > 256 )
  633.         return colorsRequestedErr;
  634.  
  635.     dataHandle = NewHandleClear(sizeof(octree));
  636.     if( dataHandle == nil )
  637.         return memFullErr;
  638.  
  639.     HLock(dataHandle);
  640.     tree = *(octree **)dataHandle;
  641.     counter = maximumLevel + 1;
  642.     while( --counter >= 0 )
  643.         tree->colorList[counter] = emptyNode;
  644.  
  645.     tree->maximumNodes = 1 + 8 + 64;    /* for level 0, 1, and 2. If the maximumLevel is three, then the next level will be colors */
  646.     if( maximumLevel > 3 )
  647.         tree->maximumNodes += (colorsRequested + 1) * (maximumLevel - 3);
  648.     tempHandle = NewHandle(tree->maximumNodes * sizeof(octreeNode));
  649.     HLock(tempHandle);
  650.     tree->nodeBase = *(octreeNode **)tempHandle;
  651.     tree->nodes = 1;
  652.     node = &tree->nodeBase[0];
  653.     node->children = 0;
  654.     node->parent = emptyNode;
  655.     counter = 8;
  656.     while( --counter >= 0 )
  657.         node->leaf[counter] = emptyNode;
  658.  
  659.     tree->maximumColors = colorsRequested + 1;
  660.     tempHandle = NewHandle(tree->maximumColors * sizeof(octreeColor));
  661.     HLock(tempHandle);
  662.     tree->colorBase = *(octreeColor **)tempHandle;
  663.  
  664.     HUnlock(dataHandle);
  665.  
  666.     *dataHandlePtr = (long)dataHandle;
  667.     *bankType = ColorBankIsCustom;
  668.     return noErr;
  669. }
  670.  
  671.  
  672. pascal short KillOctree(long dataHandle)
  673. {
  674.     octree *tree = *(octree **)dataHandle;
  675.  
  676.     DisposeHandle(RecoverHandle(tree->colorBase));
  677.     DisposeHandle(RecoverHandle(tree->nodeBase));
  678.     DisposeHandle((Handle)dataHandle);
  679.     return noErr;
  680. }
  681.  
  682.  
  683. pascal short RecordOctreeColors(long dataHandle, RGBColor *colorPtr, long colorCount, long *uniqueColorsPtr)
  684. {
  685.     octree *tree;
  686.  
  687.     HLock((Handle)dataHandle);
  688.     tree = *(octree **)dataHandle;
  689.  
  690.     while( --colorCount >= 0 ) {
  691.         AddColorToOctree(tree, colorPtr++);
  692.         if( tree->colors == tree->maximumColors )
  693.             ReduceOctree(tree);
  694.     }
  695.  
  696. /*    picture utilities actually uses this value to clip the palette entries to either the number of colors requested or
  697.     the number of unique colors in the picture, whichever is smaller. if we don’t set this field, then it will be zero
  698.     and picture utilities will always generate  a palette with  zero colors! */
  699.  
  700.     *uniqueColorsPtr = tree->colors;
  701.  
  702.     HUnlock((Handle)dataHandle);
  703.     return noErr;
  704. }
  705.  
  706.  
  707. static unsigned short Divide(register long component, register long count)
  708. {
  709.     asm {
  710.         divu.l    count, component
  711.         move.w    component, d0
  712.     }
  713. }
  714.  
  715. pascal short CalcOctreeTable(long dataHandle, short colorsRequested, short *colorBankPtr, ColorSpec *resultPtr)
  716. {
  717.     octree *tree;
  718.     octreeColor *color;
  719.     short index;
  720.     short uniqueColors;
  721.  
  722.     HLock((Handle)dataHandle);
  723.     tree = *(octree **)dataHandle;
  724.     color = &tree->colorBase[0];
  725.     uniqueColors = tree->colors;
  726.  
  727.     for(index=0; index < colorsRequested; ++index) {
  728.         resultPtr->value = index;
  729.         if( --uniqueColors >= 0 ) {
  730.             resultPtr->rgb.red = Divide(color->totalRed, color->count);
  731.             resultPtr->rgb.green = Divide(color->totalGreen, color->count);
  732.             resultPtr->rgb.blue = Divide(color->totalBlue, color->count);
  733.             ++color;
  734.         } else {
  735.             resultPtr->rgb.red = 0;
  736.             resultPtr->rgb.green = 0;
  737.             resultPtr->rgb.blue = 0;
  738.         }
  739.         ++resultPtr;
  740.     }
  741.  
  742.     HUnlock((Handle)dataHandle);
  743.     return noErr;
  744. }
  745.